{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #String Compression II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getLengthOfOptimalCompression"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #压缩字符串 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p><a href=\"https://baike.baidu.com/item/%E8%A1%8C%E7%A8%8B%E9%95%BF%E5%BA%A6%E7%BC%96%E7%A0%81/2931940?fr=aladdin\" target=\"_blank\">行程长度编码</a> 是一种常用的字符串压缩方法，它将连续的相同字符（重复 2 次或更多次）替换为字符和表示字符计数的数字（行程长度）。例如，用此方法压缩字符串 <code>&quot;aabccc&quot;</code> ，将 <code>&quot;aa&quot;</code> 替换为 <code>&quot;a2&quot;</code> ，<code>&quot;ccc&quot;</code> 替换为` <code>&quot;c3&quot;</code> 。因此压缩后的字符串变为 <code>&quot;a2bc3&quot;</code> 。</p>\n",
    "\n",
    "<p>注意，本问题中，压缩时没有在单个字符后附加计数 <code>&#39;1&#39;</code> 。</p>\n",
    "\n",
    "<p>给你一个字符串 <code>s</code> 和一个整数 <code>k</code> 。你需要从字符串 <code>s</code> 中删除最多 <code>k</code> 个字符，以使 <code>s</code> 的行程长度编码长度最小。</p>\n",
    "\n",
    "<p>请你返回删除最多 <code>k</code> 个字符后，<code>s</code> <strong>行程长度编码的最小长度</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;aaabcccd&quot;, k = 2\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>在不删除任何内容的情况下，压缩后的字符串是 &quot;a3bc3d&quot; ，长度为 6 。最优的方案是删除 &#39;b&#39; 和 &#39;d&#39;，这样一来，压缩后的字符串为 &quot;a3c3&quot; ，长度是 4 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;aabbaa&quot;, k = 2\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>如果删去两个 &#39;b&#39; 字符，那么压缩后的字符串是长度为 2 的 &quot;a4&quot; 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;aaaaaaaaaaa&quot;, k = 0\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>由于 k 等于 0 ，不能删去任何字符。压缩后的字符串是 &quot;a11&quot; ，长度为 3 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 100</code></li>\n",
    "\t<li><code>0 &lt;= k &lt;= s.length</code></li>\n",
    "\t<li><code>s</code> 仅包含小写英文字母</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [string-compression-ii](https://leetcode.cn/problems/string-compression-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [string-compression-ii](https://leetcode.cn/problems/string-compression-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"aaabcccd\"\\n2', '\"aabbaa\"\\n2', '\"aaaaaaaaaaa\"\\n0']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:\n",
    "        n=len(s)\n",
    "        f=[[inf]*(k+1) for _ in range(n+1)]\n",
    "        f[0][0]=0\n",
    "        def c(a): return 0 if a<=1 else (1 if a<=9 else (2 if a<=99 else 3))\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(0,min(i,k+1)):\n",
    "                if j<k: f[i][j+1]=min(f[i][j+1],f[i-1][j])\n",
    "                a=b=0\n",
    "                for m in range(i,n+1):\n",
    "                    if s[m-1]==s[i-1]:a+=1\n",
    "                    else: b+=1\n",
    "                    if j+b<=k: f[m][j+b]=min(f[m][j+b],c(a)+1+f[i-1][j])\n",
    "                    else: break\n",
    "        return f[n][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:\n",
    "        def f(c):\n",
    "            if c == 1:\n",
    "                return 1\n",
    "            elif c < 10:\n",
    "                return 2\n",
    "            elif c < 100:\n",
    "                return 3\n",
    "            return 4\n",
    "        n = len(s)\n",
    "        t = n - k\n",
    "        if not t:\n",
    "            return 0\n",
    "        dp = [[0 if not j else 999 for j in range(t+1)] for i in range(n+1)]\n",
    "        for j in range(1, t+1):\n",
    "            for i in range(n-1, -1, -1):\n",
    "                same = 0\n",
    "                for p in range(i, n):\n",
    "                    if s[p] == s[i]:\n",
    "                        same += 1\n",
    "                    if same == j:\n",
    "                        dp[i][j] = min(dp[i][j], f(same))\n",
    "                        break\n",
    "                    dp[i][j] = min(dp[i][j], f(same) + dp[p+1][j-same])\n",
    "                dp[i][j] = min(dp[i][j], dp[i+1][j])\n",
    "        # print(dp)\n",
    "        return dp[0][t]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:\n",
    "\n",
    "        n = len(s)\n",
    "        def cst(x): #注意长度为1的子串不压缩更优\n",
    "            return len(str(x))+1 if x>1 else x\n",
    "        \n",
    "        dp = [[10**9 for j in range(k+1)] for i in range(n)] #由于dp数组的元素总是越小越好，因此初始化为一个很大的值\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(min(i+2,k+1)): \n",
    "                if j>0: \n",
    "                    dp[i][j]=dp[i-1][j-1] if i else 0\n",
    "                same = 0\n",
    "                for ii in range(i,-1,-1): #为了维护same，内循环必须逆序遍历\n",
    "                    if s[ii]==s[i]:\n",
    "                        same+=1\n",
    "                        dp[i][j]=min(dp[i][j],dp[ii-1][j-(i-ii+1-same)]+cst(same) if ii else cst(same)) \n",
    "                    if i-ii+1-same>j: # 此时已非法状态，直接退出循环\n",
    "                        break\n",
    "                    \n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:\n",
    "        calc = lambda x: 1 if x == 1 else (2 if x < 10 else (3 if x < 100 else 4))\n",
    "\n",
    "        n = len(s)\n",
    "        f = [[10**9] * (k + 1) for _ in range(n + 1)]\n",
    "        f[0][0] = 0\n",
    "        \n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(min(k, i) + 1):\n",
    "                if j > 0:\n",
    "                    f[i][j] = f[i - 1][j - 1]\n",
    "                same = diff = 0\n",
    "                for i0 in range(i, 0, -1):\n",
    "                    if s[i0 - 1] == s[i - 1]:\n",
    "                        same += 1\n",
    "                        f[i][j] = min(f[i][j], f[i0 - 1][j - diff] + calc(same))\n",
    "                    else:\n",
    "                        diff += 1\n",
    "                        if diff > j:\n",
    "                            break\n",
    "        return f[n][k]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:\n",
    "        calc = lambda x: 1 if x == 1 else (2 if x < 10 else (3 if x < 100 else 4))\n",
    "        n = len(s)\n",
    "        f = [[10**9]*(k+1) for _ in range(n+1)]\n",
    "        f[0][0] = 0 \n",
    "        for i in range(1,n+1):\n",
    "            for j in range(min(k,i)+1):\n",
    "                if j>0: f[i][j] = f[i-1][j-1]\n",
    "                same = diff = 0\n",
    "                for i0 in range(i,0,-1):\n",
    "                    if s[i0-1] ==s[i-1]:\n",
    "                        same+=1\n",
    "                        f[i][j] = min(f[i][j],f[i0-1][j-diff]+calc(same))\n",
    "                    else:\n",
    "                        diff+=1\n",
    "                        if diff>j: break \n",
    "        return f[n][k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:\n",
    "\n",
    "        n = len(s)\n",
    "        def cst(x): #注意长度为1的子串不压缩更优\n",
    "            return len(str(x))+1 if x>1 else x\n",
    "        \n",
    "        dp = [[10**9 for j in range(k+1)] for i in range(n)] #由于dp数组的元素总是越小越好，因此初始化为一个很大的值\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(min(i+2,k+1)): \n",
    "                if j>0: \n",
    "                    dp[i][j]=dp[i-1][j-1] if i else 0\n",
    "                same = 0\n",
    "                for ii in range(i,-1,-1): #为了维护same，内循环必须逆序遍历\n",
    "                    if s[ii]==s[i]:\n",
    "                        same+=1\n",
    "                        dp[i][j]=min(dp[i][j],dp[ii-1][j-(i-ii+1-same)]+cst(same) if ii else cst(same)) \n",
    "                    if i-ii+1-same>j: # 此时已非法状态，直接退出循环\n",
    "                        break\n",
    "                    \n",
    "        return dp[-1][-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:\n",
    "        calc = lambda x: 1 if x == 1 else (2 if x < 10 else (3 if x < 100 else 4))\n",
    "\n",
    "        n = len(s)\n",
    "        f = [[10**9] * (k + 1) for _ in range(n + 1)]\n",
    "        f[0][0] = 0\n",
    "        \n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(min(k, i) + 1):\n",
    "                if j > 0:\n",
    "                    f[i][j] = f[i - 1][j - 1]\n",
    "                same = diff = 0\n",
    "                for i0 in range(i, 0, -1):\n",
    "                    if s[i0 - 1] == s[i - 1]:\n",
    "                        same += 1\n",
    "                        f[i][j] = min(f[i][j], f[i0 - 1][j - diff] + calc(same))\n",
    "                    else:\n",
    "                        diff += 1\n",
    "                        if diff > j:\n",
    "                            break\n",
    "        return f[n][k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        def cst(x):\n",
    "            return len(str(x)) + 1 if x > 1 else x\n",
    "        dp = [[10**9 for j in range(k+1)] for i in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(min(i+2, k+1)):\n",
    "                if j > 0:\n",
    "                    dp[i][j] = dp[i-1][j-1] if i else 0\n",
    "                same = 0\n",
    "                for ii in range(i, -1, -1):\n",
    "                    if s[ii] == s[i]:\n",
    "                        same += 1\n",
    "                        dp[i][j] = min(dp[i][j], dp[ii-1][j-(i-ii+1-same)]+cst(same) if ii else cst(same))\n",
    "                    if i-ii+1-same > j:\n",
    "                        break\n",
    "\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:\n",
    "        calc = lambda x: 1 if x == 1 else (2 if x < 10 else (3 if x < 100 else 4))\n",
    "\n",
    "        n = len(s)\n",
    "        f = [[10**9] * (k + 1) for _ in range(n + 1)]\n",
    "        f[0][0] = 0\n",
    "        \n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(min(k, i) + 1):\n",
    "                if j > 0:\n",
    "                    f[i][j] = f[i - 1][j - 1]\n",
    "                same = diff = 0\n",
    "                for i0 in range(i, 0, -1):\n",
    "                    if s[i0 - 1] == s[i - 1]:\n",
    "                        same += 1\n",
    "                        f[i][j] = min(f[i][j], f[i0 - 1][j - diff] + calc(same))\n",
    "                    else:\n",
    "                        diff += 1\n",
    "                        if diff > j:\n",
    "                            break\n",
    "        return f[n][k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:\n",
    "        n=len(s)\n",
    "        f=[[inf]*(k+1) for _ in range(n+1)]\n",
    "        f[0][0]=0\n",
    "        def c(a): return 0 if a<=1 else (1 if a<=9 else (2 if a<=99 else 3))\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(0,min(i,k+1)):\n",
    "                if j<k: f[i][j+1]=min(f[i][j+1],f[i-1][j])\n",
    "                a=0\n",
    "                b=0\n",
    "                for m in range(i,n+1):\n",
    "                    if s[m-1]==s[i-1]:a+=1\n",
    "                    else: b+=1\n",
    "                    if j+b<=k: f[m][j+b]=min(f[m][j+b],c(a)+1+f[i-1][j])\n",
    "        return f[n][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:\n",
    "        dp = [[0]*(k+1) for _ in range(len(s)+1)]\n",
    "        char = None\n",
    "        count = 0\n",
    "        l = 0\n",
    "        for i in range(1,len(s)+1):\n",
    "            cur_char = s[i-1]\n",
    "            if cur_char == char:\n",
    "                count += 1\n",
    "                dp[i][0] = l + len(str(count))\n",
    "            else:\n",
    "                if count > 1:\n",
    "                    l += len(str(count))\n",
    "                l += 1\n",
    "                count = 1\n",
    "                dp[i][0] = l\n",
    "                char = cur_char\n",
    "                \n",
    "        for i in range(1,len(s)+1):\n",
    "            char = s[i-1]\n",
    "            for j in range(1,min(k,i)+1):\n",
    "                dp[i][j] = dp[i-1][j-1]\n",
    "                m = 0\n",
    "                for b in range(i,0,-1):\n",
    "                    if s[b-1] == char:\n",
    "                        m += 1\n",
    "                        if (i-b+1-m) <= j:\n",
    "                            l = 1\n",
    "                            if m > 1:\n",
    "                                l += len(str(m))\n",
    "                            dp[i][j] = min(dp[i][j], dp[b-1][j-i+b+m-1] + l)\n",
    "                        else:\n",
    "                            break\n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:\n",
    "\n",
    "        n = len(s)\n",
    "        def cst(x):\n",
    "            return len(str(x))+1 if x>1 else x\n",
    "        \n",
    "        dp = [[10**9 for j in range(k+1)] for i in range(n)]\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(min(i+2,k+1)):\n",
    "                if j>0: \n",
    "                    dp[i][j]=dp[i-1][j-1] if i else 0\n",
    "                same = 0\n",
    "                for ii in range(i,-1,-1):\n",
    "                    if s[ii]==s[i]:\n",
    "                        same+=1\n",
    "                        dp[i][j]=min(dp[i][j],dp[ii-1][j-(i-ii+1-same)]+cst(same) if ii else cst(same)) \n",
    "                    if i-ii+1-same>j:\n",
    "                        break\n",
    "                    \n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:\n",
    "        n=len(s)\n",
    "        f=[[inf]*(k+1) for _ in range(n+1)]\n",
    "        f[0][0]=0\n",
    "        def c(a): return 0 if a<=1 else (1 if a<=9 else (2 if a<=99 else 3))\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(0,min(i,k+1)):\n",
    "                if j<k: f[i][j+1]=min(f[i][j+1],f[i-1][j])\n",
    "                a=b=0\n",
    "                for m in range(i,n+1):\n",
    "                    if s[m-1]==s[i-1]:a+=1\n",
    "                    else: b+=1\n",
    "                    if j+b<=k: f[m][j+b]=min(f[m][j+b],c(a)+1+f[i-1][j])\n",
    "                    else: break\n",
    "        return f[n][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getEncodedSameLength(self, k):\n",
    "        # 求：当有k个相同字符'a'的时候，编码后数字部分的长度\n",
    "\n",
    "        # 假设重复的字符是'a'\n",
    "        # 如果k == 0, 原字符串是空字符串；如果k == 1，原字符串是'a',编码后是'a', 这两种情况数字部分的长度都是0\n",
    "        # 如果k是个位数，假设原字符串是'aaaa',编码后变为'a4'，数字部分的长度是1\n",
    "        # 如果k是个两位数字，编码后数字部分的长度是2\n",
    "        # 由于1 <= s.length <= 100，0 <= k <= s.length，所以k最大是100,此时编码后数字部分的长度是3\n",
    "        if k <= 1:  return 0\n",
    "        elif 1 < k < 10:    return 1\n",
    "        elif 10 <= k < 100: return 2\n",
    "        else:   return 3\n",
    "\n",
    "    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        \n",
    "        # dp[i][j] 表示从前i个字符中最多选择j个字符进行删除\n",
    "        dp = [[float('inf')] * (k + 1) for _ in range(n + 1)]\n",
    "        # 从前0个字符删除任意个字符，长度都是0, 所以把dp[0]都设成0\n",
    "        dp[0] = [0] * (k + 1)\n",
    "\n",
    "        # 每轮i代表，本轮在考虑怎么删除前i个字符\n",
    "        # 需要考虑1到n次\n",
    "        for i in range(1, n + 1):\n",
    "            \n",
    "            # j代表，我们最多从前i个字符中删除j个字符 => 可得限制条件1：最多只能删除i个\n",
    "            # 由于题目要求最多只能删除k个 => 可得限制条件2：最多只能删除k个\n",
    "            # 根据限制条件1、2可得, j的范围是0到min(k, i)\n",
    "            for j in range(min(k + 1, i + 1)):\n",
    "                \n",
    "                # 如果此时的j小于k, 代表我们可以考虑删除第i个字符\n",
    "                if j < k:\n",
    "                    # dp的更新可以参照原题解中的第三条 “如果删除字符i，则此时dp[i][j] = dp[i-1][j-1]”\n",
    "                    # 如果我们此时删除第i个字符, j需要加一，所以此时需要更新j + 1的位置\n",
    "                    # dp[i][j + 1]是不删除第i个字符，dp[i - 1][j]是删除第i个字符\n",
    "                    dp[i][j + 1] = min(dp[i][j + 1], dp[i - 1][j])\n",
    "\n",
    "                # 保留第i个字符\n",
    "                # 保留部分对dp的更新可以参照原题解中的第四条\n",
    "                # “如果保留字符i, 则此时后续尽量选择保留与字符i相同的字符”\n",
    "\n",
    "                # m遍历i到n\n",
    "                # same代表字符i后面，和字符i相同的字符个数\n",
    "                # dele代表字符i后面，我们想要删除的字符个数\n",
    "                same, dele = 0, 0\n",
    "                for m in range(i, n + 1):\n",
    "                    if s[m - 1] == s[i - 1]:\n",
    "                        same += 1\n",
    "                    else:\n",
    "                        dele += 1\n",
    "\n",
    "                    # 当已经删除的字符个数j与想要删除的字符个数dele之和大于k\n",
    "                    # 说明我们已经删除了足够多的字符，当前m后面的字符都不能删除，所以break\n",
    "                    if j + dele > k:    break\n",
    "\n",
    "                    # 考虑要不要真的删除我们想要删除的字符\n",
    "                    # dp更新方法参考原题解中的第三条 “如果删除字符i，则此时dp[i][j] = dp[i-1][j-1]”\n",
    "                    \n",
    "                    # 如果我们不删除这dele个字符，此时编码的长度是dp[m][j + dele]\n",
    "                    # 如果我们删除dele个字符，此时编码的长度是 dp[i - 1][j] + self.getEncodedSameLength(same) + 1\n",
    "                    # dp[i - 1][j]代表前i - 1个字符删除j个之后的编码长度\n",
    "                    # 由于删除dele个字符后，i到m个字符会变成same个连续的字符，所以 i到m的编码长度由self.getEncodedSameLength(same) + 1表示\n",
    "                    dp[m][j + dele] = min(dp[m][j + dele], dp[i - 1][j] + self.getEncodedSameLength(same) + 1)\n",
    "\n",
    "        return dp[n][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:\n",
    "        calc = lambda x: 1 if x == 1 else (2 if x < 10 else (3 if x < 100 else 4))\n",
    "        n=len(s)\n",
    "        f=[[10**9]*(k+1) for _ in range(n+1)]\n",
    "        f[0][0]=0\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(min(k,i)+1):\n",
    "                if j>0:\n",
    "                    f[i][j]=f[i-1][j-1]\n",
    "                same=diff=0\n",
    "                for i0 in range(i,0,-1):\n",
    "                    if s[i0-1]==s[i-1]:\n",
    "                        same+=1\n",
    "                        f[i][j]=min(f[i][j],f[i0-1][j-diff]+calc(same))\n",
    "                    else:\n",
    "                        diff+=1\n",
    "                        if diff>j:\n",
    "                            break\n",
    "        \n",
    "        return f[n][k]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:\n",
    "        def cal(length):\n",
    "            if length == 1:\n",
    "                return 1 \n",
    "            elif length < 10:\n",
    "                return 2 \n",
    "            elif length < 100:\n",
    "                return 3\n",
    "            else:\n",
    "                return 4 \n",
    "        n = len(s)\n",
    "        dp = [[float('inf') for _ in range(k + 1)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(k + 1):\n",
    "                same = 0\n",
    "                diff = 0\n",
    "                if j > 0:\n",
    "                    dp[i][j] = dp[i - 1][j - 1] if i > 0 else 0\n",
    "                for p in range(i, - 1, - 1):\n",
    "                    if s[p] == s[i]:\n",
    "                        same += 1 \n",
    "                    else:\n",
    "                        diff += 1 \n",
    "                    if diff > j:\n",
    "                        break\n",
    "                    dp[i][j] = min(dp[i][j], (dp[p - 1][j - diff] if p > 0 else 0) + cal(same))\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:\n",
    "        def calx(x):\n",
    "            if x==1:\n",
    "                return 1\n",
    "            if x<10:\n",
    "                return 2\n",
    "            if x<100:\n",
    "                return 3\n",
    "            return 4\n",
    "        n=len(s)\n",
    "        dp=[[float(\"inf\") for _ in range(k+1)]for _ in range(n+1)]\n",
    "        dp[0][0]=0\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(min(k,i)+1):\n",
    "                if j>0:\n",
    "                    dp[i][j]=dp[i-1][j-1]\n",
    "                same,diff=0,0\n",
    "                for l in range(i,0,-1):\n",
    "                    if s[l-1]==s[i-1]:\n",
    "                        same+=1\n",
    "                        dp[i][j]=min(dp[i][j],dp[l-1][j-diff]+calx(same))\n",
    "                    else:\n",
    "                        diff+=1\n",
    "                        if diff>j:\n",
    "                            break\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "动态规划\n",
    "f[i][j] 表示对于原串 s 的前 i 个字符，通过删除其中的 j 个字符，\n",
    "剩余的 i−j 个字符可以得到的最小的压缩串的长度。\n",
    "\n",
    "'''\n",
    "class Solution:\n",
    "    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:\n",
    "        calc = lambda x: 1 if x == 1 else (2 if x < 10 else (3 if x < 100 else 4))\n",
    "\n",
    "        n = len(s)\n",
    "        f = [[10**9] * (k + 1) for _ in range(n + 1)]\n",
    "        f[0][0] = 0\n",
    "        \n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(min(k, i) + 1):\n",
    "                if j > 0:\n",
    "                    f[i][j] = f[i - 1][j - 1]\n",
    "                same = diff = 0\n",
    "                for i0 in range(i, 0, -1):\n",
    "                    if s[i0 - 1] == s[i - 1]:\n",
    "                        same += 1\n",
    "                        f[i][j] = min(f[i][j], f[i0 - 1][j - diff] + calc(same))\n",
    "                    else:\n",
    "                        diff += 1\n",
    "                        if diff > j:\n",
    "                            break\n",
    "        return f[n][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[float('inf')] * (k + 1) for _ in range(n + 1)]\n",
    "        dp[0][0] = 0\n",
    "\n",
    "        def calc(same):\n",
    "            if same == 1:\n",
    "                return 1\n",
    "            elif 1 < same < 10:\n",
    "                return 2\n",
    "            elif 10 <= same < 100:\n",
    "                return 3\n",
    "            else:\n",
    "                return 4\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(min(k, i) + 1):\n",
    "                if j > 0:\n",
    "                    dp[i][j] = dp[i - 1][j - 1]\n",
    "                \n",
    "                same, diff = 0, 0\n",
    "                for m in range(i, 0, -1):\n",
    "                    if s[m - 1] == s[i - 1]:\n",
    "                        same += 1\n",
    "                        dp[i][j] = min(dp[i][j], dp[m - 1][j - diff] + calc(same))\n",
    "                    else:\n",
    "                        diff += 1\n",
    "                        if diff > j:\n",
    "                            break\n",
    "        return dp[n][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:\n",
    "        def cal(length):\n",
    "            if length == 1:\n",
    "                return 1 \n",
    "            elif length < 10:\n",
    "                return 2 \n",
    "            elif length < 100:\n",
    "                return 3\n",
    "            else:\n",
    "                return 4 \n",
    "        n = len(s)\n",
    "        dp = [[float('inf') for _ in range(k + 1)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(k + 1):\n",
    "                same = 0\n",
    "                diff = 0\n",
    "                if j > 0:\n",
    "                    dp[i][j] = dp[i - 1][j - 1] if i > 0 else 0\n",
    "                for p in range(i, - 1, - 1):\n",
    "                    if s[p] == s[i]:\n",
    "                        same += 1 \n",
    "                    else:\n",
    "                        diff += 1 \n",
    "                    if diff > j:\n",
    "                        break\n",
    "                    dp[i][j] = min(dp[i][j], (dp[p - 1][j - diff] if p > 0 else 0) + cal(same))\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:\n",
    "        def cal(length):\n",
    "            if length == 1:\n",
    "                return 1 \n",
    "            elif length < 10:\n",
    "                return 2 \n",
    "            elif length < 100:\n",
    "                return 3\n",
    "            else:\n",
    "                return 4 \n",
    "        n = len(s)\n",
    "        dp = [[float('inf') for _ in range(k + 1)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(k + 1):\n",
    "                same = 0\n",
    "                diff = 0\n",
    "                if j > 0:\n",
    "                    dp[i][j] = dp[i - 1][j - 1] if i > 0 else 0\n",
    "                for p in range(i, - 1, - 1):\n",
    "                    if s[p] == s[i]:\n",
    "                        same += 1 \n",
    "                    else:\n",
    "                        diff += 1 \n",
    "                    if diff > j:\n",
    "                        break\n",
    "                    dp[i][j] = min(dp[i][j], (dp[p - 1][j - diff] if p > 0 else 0) + cal(same))\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "from math import log10\n",
    "\n",
    "class Solution:\n",
    "    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:\n",
    "        last_char = None\n",
    "        last_count = None\n",
    "        last_pos = None\n",
    "        last_same = [None] * 26\n",
    "        segments = []\n",
    "        def _submit(i):\n",
    "            lci = ord(last_char) - ord(\"a\")\n",
    "            if last_same[lci] is None:\n",
    "                segments.append((last_count, None, None, i))\n",
    "            else:\n",
    "                segments.append((last_count, last_same[lci][0], i - last_count - last_same[lci][1], i))\n",
    "            last_same[lci] = (len(segments) - 1, i)\n",
    "        for i, c in enumerate(s):\n",
    "            if last_char != c:\n",
    "                if last_char is not None:\n",
    "                    _submit(i)\n",
    "                last_char = c\n",
    "                last_count = 1\n",
    "            else:\n",
    "                last_count += 1\n",
    "        _submit(len(s))\n",
    "\n",
    "        def all_valid_reduce(x, limit):\n",
    "            if x == 1:\n",
    "                yield 0, 0\n",
    "            else:\n",
    "                current_len = int(log10(x)) + 1\n",
    "                yield 0, current_len\n",
    "                next_len = current_len - 1\n",
    "                next_num = max(10 ** next_len - 1, 1)\n",
    "                while x - next_num < limit:\n",
    "                    yield x - next_num, next_len\n",
    "                    if not next_len:\n",
    "                        break\n",
    "                    next_num /= 10\n",
    "                    next_num = max(next_num, 1)\n",
    "                    next_len -= 1\n",
    "\n",
    "        @lru_cache(maxsize=None)\n",
    "        def search(i, k):\n",
    "            if i < 0:\n",
    "                return 0\n",
    "            if segments[i][3] <= k:\n",
    "                return 0\n",
    "            if i == 0:\n",
    "                return next(all_valid_reduce(segments[0][0] - k, 1))[1] + 1\n",
    "            else:\n",
    "                count, prev, prev_remove, _ = segments[i]\n",
    "                ans = 1000\n",
    "                for k_, l in all_valid_reduce(count, k + 1):\n",
    "                    ans = min(ans, search(i - 1, k - k_) + 1 + l)\n",
    "                if k >= count:\n",
    "                    ans = min(ans, search(i - 1, k - count))\n",
    "                total_count = count\n",
    "                while prev is not None:\n",
    "                    k -= prev_remove\n",
    "                    if k < 0:\n",
    "                        break\n",
    "                    count2, prev2, prev_remove, _ = segments[prev]\n",
    "                    total_count += count2\n",
    "                    for k_, l in all_valid_reduce(total_count, min(count, k + 1)):\n",
    "                        ans = min(ans, search(prev - 1, k - k_) + 1 + l)\n",
    "                    prev = prev2\n",
    "                return ans\n",
    "        return search(len(segments) - 1, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:\n",
    "        def cost(same):\n",
    "            if same == 1:\n",
    "                return 1\n",
    "            elif same < 10:\n",
    "                return 2\n",
    "            elif same < 100:\n",
    "                return 3\n",
    "            else:\n",
    "                return 4\n",
    "            \n",
    "        @cache\n",
    "        def dp(idx, t):\n",
    "            if idx == 0 and t < 2:\n",
    "                return 0\n",
    "\n",
    "            if idx + 1 < t:\n",
    "                return inf\n",
    "\n",
    "            ret = inf\n",
    "            if t > 0:\n",
    "                ret = min(ret, dp(idx - 1, t - 1))\n",
    "\n",
    "            same = 0\n",
    "            diff = 0\n",
    "\n",
    "            for i in range(idx, 0, -1):\n",
    "                if s[i - 1] == s[idx - 1]:\n",
    "                    same += 1\n",
    "                    ret = min(ret, dp(i - 1, t - diff) + cost(same))\n",
    "                else:\n",
    "                    diff += 1\n",
    "\n",
    "                    if diff > t:\n",
    "                        break\n",
    "            \n",
    "            return ret\n",
    "            \n",
    "        return dp(len(s), k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        memo = {}\n",
    "        \n",
    "        # Helper function to compute compression length of continuous characters\n",
    "        def get_compressed_length(count):\n",
    "            if count == 1:\n",
    "                return 1\n",
    "            elif count < 10:\n",
    "                return 2\n",
    "            elif count < 100:\n",
    "                return 3\n",
    "            else:\n",
    "                return 4\n",
    "\n",
    "        # Recursive function\n",
    "        def dp(i, k):\n",
    "            # If we've exceeded allowable deletions, return a large value\n",
    "            if k < 0:\n",
    "                return float('inf')\n",
    "            \n",
    "            # If we've processed the entire string, return 0\n",
    "            if i >= n:\n",
    "                return 0\n",
    "            \n",
    "            if (i, k) in memo:\n",
    "                return memo[(i, k)]\n",
    "            \n",
    "            # Case 1: delete current character\n",
    "            ans = dp(i + 1, k - 1)\n",
    "            \n",
    "            # Case 2: keep current character and try different compression lengths\n",
    "            count = 0\n",
    "            diff_char_count = 0\n",
    "            j = i\n",
    "            while j < n and diff_char_count <= k:\n",
    "                if s[j] == s[i]:\n",
    "                    count += 1\n",
    "                else:\n",
    "                    diff_char_count += 1\n",
    "                ans = min(ans, get_compressed_length(count) + dp(j + 1, k - diff_char_count))\n",
    "                j += 1\n",
    "\n",
    "            memo[(i, k)] = ans\n",
    "            return ans\n",
    "        \n",
    "        return dp(0, k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        ## 把删k个，转换为从n个里选择c个        \n",
    "        c = n - k\n",
    "\n",
    "        def calc(c):\n",
    "            if c == 1:\n",
    "                return 1\n",
    "            elif c < 10:\n",
    "                return 2\n",
    "            elif c < 100:\n",
    "                return 3\n",
    "            return 4\n",
    "            \n",
    "        @cache\n",
    "        def dp(i, k):\n",
    "            if k > c:\n",
    "                return inf\n",
    "            if i == n:\n",
    "                # 最终状态，如果正好选择c个，说明是一个可行解，否则不可行，返回inf\n",
    "                if k == c:\n",
    "                    return 0\n",
    "                else:\n",
    "                    return inf\n",
    "            # 不选择\n",
    "            t = dp(i+1, k)\n",
    "            same = 0\n",
    "            for j in range(i, n):\n",
    "                if s[i] == s[j]:\n",
    "                    same += 1\n",
    "                    # 选择same个\n",
    "                    t = min(t, dp(j+1,k+same) + calc(same))\n",
    "            return t\n",
    "        return dp(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:\n",
    "\n",
    "        n = len(s)\n",
    "        \n",
    "        def check(cur):\n",
    "            if cur <= 1:\n",
    "                return cur\n",
    "            if cur > 99:\n",
    "                return 4\n",
    "            elif cur > 9:\n",
    "                return 3\n",
    "            else:\n",
    "                return 2\n",
    "        @cache\n",
    "        def dfs(cur, cnt):\n",
    "            if cnt > n - k:\n",
    "                return inf\n",
    "            if cur == n:\n",
    "                if cnt == n - k:\n",
    "                    return 0\n",
    "                return inf\n",
    "            res = dfs(cur + 1, cnt)\n",
    "            same = 0\n",
    "            for j in range(cur, n):\n",
    "                if s[j] == s[cur]:\n",
    "                    same += 1\n",
    "                    res = min(res, dfs(j + 1, cnt + same) + check(same))\n",
    "            return res\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:\n",
    "\n",
    "        n = len(s)\n",
    "        \n",
    "        def check(cur):\n",
    "            if cur <= 1:\n",
    "                return cur\n",
    "            if cur > 99:\n",
    "                return 4\n",
    "            elif cur > 9:\n",
    "                return 3\n",
    "            else:\n",
    "                return 2\n",
    "        @cache\n",
    "        def dfs(cur, cnt):\n",
    "            if cnt > n - k:\n",
    "                return inf\n",
    "            if cur == n:\n",
    "                if cnt == n - k:\n",
    "                    return 0\n",
    "                return inf\n",
    "            res = dfs(cur + 1, cnt)\n",
    "            same = 0\n",
    "            for j in range(cur, n):\n",
    "                if s[j] == s[cur]:\n",
    "                    same += 1\n",
    "                    res = min(res, dfs(j + 1, cnt + same) + check(same))\n",
    "            return res\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        ## 把删k个，转换为从n个里选择c个        \n",
    "        c = n - k\n",
    "\n",
    "        def calc(c):\n",
    "            if c == 1:\n",
    "                return 1\n",
    "            elif c < 10:\n",
    "                return 2\n",
    "            elif c < 100:\n",
    "                return 3\n",
    "            return 4\n",
    "            \n",
    "        @cache\n",
    "        def dp(i, k):\n",
    "            if k > c:\n",
    "                return inf\n",
    "            if i == n:\n",
    "                # 最终状态，如果正好选择c个，说明是一个可行解，否则不可行，返回inf\n",
    "                if k == c:\n",
    "                    return 0\n",
    "                else:\n",
    "                    return inf\n",
    "            # 不选择\n",
    "            t = dp(i+1, k)\n",
    "            same = 0\n",
    "            for j in range(i, n):\n",
    "                if s[i] == s[j]:\n",
    "                    same += 1\n",
    "                    # 选择same个\n",
    "                    t = min(t, dp(j+1,k+same) + calc(same))\n",
    "            return t\n",
    "        return dp(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        ## 把删k个，转换为从n个里选择c个        \n",
    "        c = n - k\n",
    "\n",
    "        def calc(c):\n",
    "            if c == 1:\n",
    "                return 1\n",
    "            elif c < 10:\n",
    "                return 2\n",
    "            elif c < 100:\n",
    "                return 3\n",
    "            return 4\n",
    "            \n",
    "        @cache\n",
    "        def dp(i, k):\n",
    "            if k > c:\n",
    "                return inf\n",
    "            if i == n:\n",
    "                # 最终状态，如果正好选择c个，说明是一个可行解，否则不可行，返回inf\n",
    "                if k == c:\n",
    "                    return 0\n",
    "                else:\n",
    "                    return inf\n",
    "            # 不选择\n",
    "            t = dp(i+1, k)\n",
    "            same = 0\n",
    "            for j in range(i, n):\n",
    "                if s[i] == s[j]:\n",
    "                    same += 1\n",
    "                    # 选择same个\n",
    "                    t = min(t, dp(j+1,k+same) + calc(same))\n",
    "            return t\n",
    "        return dp(0, 0)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
